package org.ala.tiktools.tools.queue;

/**
 *	双链实现
 *
 *	@author ala
 *	@date 2025年4月26日
 */
public class DoubleLinkedQueue<E> implements IQueue<E> {
	/**
	 * 	首尾
	 */
	protected Node<E> HEAD, TAIL;
	/**
	 * 	
	 */
	protected int size;
	/**
	 * 	迭代器
	 */
	protected QueueIterator iterator;
	
	
	public DoubleLinkedQueue() {
		HEAD = new Node<E>(null);
		TAIL = new Node<E>(null);
		HEAD.next = TAIL; TAIL.prev = HEAD;
		size = 0;
		iterator = new QueueIterator();
	}
	public DoubleLinkedQueue(E[] datas) {
		HEAD = new Node<E>(null);
		TAIL = new Node<E>(null);
		HEAD.next = TAIL; TAIL.prev = HEAD;
		size = 0;
		iterator = new QueueIterator();
		
		for (E e : datas) {
			addLast(e);
		}
	}
	
	
	/**
	 * 	后插
	 */
	protected void addAfter(E e, Node<E> n) {
		Node<E> node = new Node<>(e);
		Node<E> nxt = n.next;
		n.next = node; node.next = nxt;
		nxt.prev = node; node.prev = n;
	}
	/**
	 * 	前插
	 */
	protected void addBefore(E e, Node<E> n) {
		Node<E> node = new Node<>(e);
		Node<E> prv = n.prev;
		prv.next = node; node.next = n;
		n.prev = node; node.prev = prv;
	}
	/**
	 * 	删除节点
	 */
	protected void remove(Node<E> n) {
		Node<E> prv = n.prev, nxt = n.next;
		prv.next = nxt; nxt.prev = prv;
		n.clear();
		size--;
	}
	
	
	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	@Override
	public int size() {
		return size;
	}
	
	
	@Override
	public boolean addFirst(E e) {
		addAfter(e, HEAD);
		size++;
		return true;
	}
	@Override
	public E removeFirst() {
		if (size == 0) {return null;}
		E v = HEAD.next.val;
		remove(HEAD.next);
		size--;
		return v;
	}
	@Override
	public E first() {
		if (size == 0) {return null;}
		return HEAD.next.val;
	}
	
	
	@Override
	public boolean addLast(E e) {
		addBefore(e, TAIL);
		size++;
		return true;
	}
	@Override
	public E removeLast() {
		if (size == 0) {return null;}
		E v = TAIL.prev.val;
		remove(TAIL.prev);
		size--;
		return v;
	}
	@Override
	public E last() {
		if (size == 0) {return null;}
		return TAIL.prev.val;
	}

	
	@Override
	public IQueueIterator<E> firstIterator() {
		iterator.resetFirst();
		return iterator;
	}

	@Override
	public IQueueIterator<E> lastIterator() {
		iterator.resetLast();
		return iterator;
	}


	/**
	 * 	全部清空助消化
	 */
	@Override
	public void clear() {
		Node<E> crt = HEAD.next;
		while (crt != TAIL) {
			Node<E> nxt = crt.next;
			remove(crt);
			crt = nxt;
		}
		HEAD.next = TAIL; TAIL.prev = HEAD;
		size = 0;
	}


	/**
	 * 	迭代器
	 */
	public class QueueIterator implements IQueueIterator<E> {
		protected Node<E> crt;
		protected QueueIterator() {
			crt = null;
		}
		
		
		/**
		 * 	在当前位置的后面插入元素
		 */
		@Override
		public boolean insert(E e) {
			DoubleLinkedQueue.this.addAfter(e, crt);
			return true;
		}
		@Override
		public void clear() {
			HEAD = TAIL = null;
			crt = null;
		}
		@Override
		public E current() {
			if (crt == null) { return null; }
			return crt.val;
		}
		
		
		/*************************************************************************************************************
		 * 	从前往后遍历
		 *************************************************************************************************************/
		@Override
		public void resetFirst() {
			crt = HEAD.next;			
		}
		@Override
		public boolean hasNext() {
			return crt != null && crt != TAIL;
		}
		@Override
		public E next() {
			E e = crt.val;
			crt = crt.next;
			return e;
		}
		@Override
		public E removeAndNext() {
			Node<E> n = crt.next;
			E e = crt.val;
			DoubleLinkedQueue.this.remove(crt);
			crt = n;
			return e;
		}


		/*************************************************************************************************************
		 * 	从后往前遍历
		 *************************************************************************************************************/
		@Override
		public void resetLast() {
			crt = TAIL.prev;
		}
		@Override
		public boolean hasPrev() {
			return crt != null && crt != HEAD;
		}
		@Override
		public E prev() {
			E e = crt.val;
			crt = crt.prev;
			return e;
		}
		@Override
		public E removeAndPrev() {
			Node<E> n = crt.prev;
			E e = crt.val;
			DoubleLinkedQueue.this.remove(crt);
			crt = n;
			return e;
		}


	}
	/**
	 * 	节点
	 */
	public static class Node<E> {
		protected Node<E> prev, next;
		protected E val;
		protected Node(E e) {this.val = e;}
		void clear() {
			prev = next = null;
			val = null;
		}
		public Node<E> getPrev() {
			return prev;
		}
		public void setPrev(Node<E> prev) {
			this.prev = prev;
		}
		public Node<E> getNext() {
			return next;
		}
		public void setNext(Node<E> next) {
			this.next = next;
		}
		public E getVal() {
			return val;
		}
		public void setVal(E val) {
			this.val = val;
		}
	}
	
	
	/**
	 * 	
	 */
	public String toString() {
		StringBuilder sbuf = new StringBuilder();
		sbuf.append("{type:Linked, size:").append(size).append(", datas:[");
		Node<E> crt = HEAD.next;
		while (crt != TAIL) {
			sbuf.append(crt.val).append(",");
			crt = crt.next;
		}
		sbuf.append("]}");
		return sbuf.toString();
	}
}
